


    public class MySingleList {
        static class ListNode {
            public int val; // 节点的值域
            public ListNode next; // 下一个节点的地址

            public ListNode(int val) {
                this.val = val;
            }
        }


        public ListNode head; // 表示当前链表的头节点

        // 在链表头部插入节点
        //一般建议，再插入的时候，先绑定后面的节点信息
        //就算链表中一个代码都没有，也不影响我们插入节点
        //以头插法插入，数据是倒序的
        public void insertAtHead(int val) {
            ListNode newNode = new ListNode(val);
            newNode.next = head;
            head = newNode;
        }

        // 在链表尾部插入节点
        public void insertAtTail(int val) {
            ListNode newNode = new ListNode(val);
            //如果head等于null,就不存在curr.next
            //cur = null 代表把链表的每一个节点都遍历完了
            //cur.next = null 代表cur现在是最后一个节的位置
            if (head == null) {
                head = newNode;
            } else {
                ListNode curr = head;
                while (curr.next != null) {
                    curr = curr.next;
                }
                curr.next = newNode;
            }
        }

        //得到单链表的长度
        public int size() {
            int length = 0;
            ListNode curr = head;
            while (curr != null) {
                length++;
                curr = curr.next;
            }
            return length;
        }

        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key) {
            ListNode curr = head;
            while (curr != null) {
                if (curr.val == key) {
                    return true;
                }
                curr = curr.next;
            }
            return false;
        }

        //删除第一次出现关键字为key的节点
        //找到指定删除的节点的前一个节点,即找到key的前驱
        public void deleteNode(int key) {
            if (head == null) {
                return;
            }
            //单独删除头节点
            if (head.val == key) {
                head = head.next;
                return;
            }
            ListNode curr = head;
            while (curr.next != null) {
                if (curr.next.val == key) {
                    curr.next = curr.next.next;
                    return;
                }
                curr = curr.next;
            }
        }

        //删除第一次出现关键字为key的节点 ------2
        public void remove(int key){
            if(head == null) {
                return;
            }
            //单独删除头节点
            if(head.val == key) {
                head = head.next;
                return;
            }
            ListNode cur = searchPrev(key);
            if(cur == null) {
                System.out.println("没有你要删除的数字");
                return;
            }
            ListNode del = cur.next;
            cur.next = del.next;
        }
        private ListNode searchPrev(int key) {
            ListNode cur = head;
            while (cur.next != null) {
                if(cur.next.val == key) {
                    return cur;
                }
                cur = cur.next;
            }
            return null;
        }

        // 删除所有值为key的节点
        public void removeAllKey(int key) {
            ListNode dummy = new ListNode(0); // 创建一个虚拟头节点，方便处理头节点的情况
            dummy.next = head;
            ListNode prev = dummy;
            ListNode curr = head;

            while (curr != null) {
                if (curr.val == key) {
                    prev.next = curr.next;
                } else {
                    prev = curr;
                }
                curr = curr.next;
            }

            head = dummy.next;
        }


        //任意位置插入,第一个数据节点为0号下标
        public void insertAtIndex(int index, int val) {
            if (index < 0) {
                throw new IndexOutOfBoundsException("Invalid index: " + index);
            }
            if (index == 0) {
                insertAtHead(val);
                return;
            }
            if(index==size()){
                insertAtTail(val);
                return;
            }
            ListNode newNode = new ListNode(val);
            ListNode curr = head;
            int count = 0;//定义一个计数器
            while (curr != null && count < index - 1) {
                curr = curr.next;
                count++;
            }
            if (curr == null) {
                throw new IndexOutOfBoundsException("Invalid index: " + index);
            }
            newNode.next = curr.next;
            curr.next = newNode;
        }


        // 遍历链表并打印节点值
        public void display() {
            //不可以让head本身移动，否则将遗失head的位置
            ListNode curr = head;
            while (curr != null) {
                System.out.print(curr.val + " ");
                curr = curr.next;
            }
            System.out.println();
        }



        // 清空链表
        public void clear() {
            head = null;
        }

    }

/*
  public class   MySingleList {
      static class ListNode {
          public int val; // 节点的值域
          public ListNode next; // 下一个节点的地址

          public ListNode(int val) {
              this.val = val;
          }
      }

      public ListNode head; // 表示当前链表的头节点

      //我们先来写一个最笨的方法：手动创建链表节点
      public void createlist() {
          // 创建链表节点
          head = new MySingleList.ListNode(-1);
          MySingleList.ListNode node1 = new MySingleList.ListNode(12);
          MySingleList.ListNode node2 = new MySingleList.ListNode(23);
          MySingleList.ListNode node3 = new MySingleList.ListNode(34);
          MySingleList.ListNode node4 = new MySingleList.ListNode(45);
          MySingleList.ListNode node5 = new MySingleList.ListNode(56);

          // 构建链表关系
          head.next = node1;
          node1.next = node2;
          node2.next = node3;
          node3.next = node4;
          node4.next = node5;

      }

  }

*/

